Dynamic Network Flows - Chapter 2: Static Flows

$(x_e) \in \IR^E$ (edge-based) $s$,$t$-flow:

$0 \leq x_e \leq \nu_e$ for all $e \in E$
$\sum_{e \in \edgesTo{v}}x_e = \sum_{e \in \edgesFrom{v}}x_e$ for all $v \in V\setminus\Set{s,t}$
$\mathrm{value}(x)\coloneqq \sum_{e \in \edgesTo{t}}x_e - \sum_{e \in \edgesFrom{t}}x_e \geq 0$

$(x_p) \in \IR^{\PathSet\cup\CycleSet}$ path-cycle-based $s$,$t$-flow:

$0 \leq x_p$ for all $p \in \PathSet\cup\CycleSet$
$\mathrm{value}(x)\coloneqq \sum_{p \in \PathSet}x_p$

$(x_e) \in \IR^E$ network-loading of $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ and $(x_p)$ path-cycle-decomposition of $(x_e)$ if $x_e = \sum_{p \in \PathSet\cup\CycleSet: e \in p}x_p$ f.a. $e \in E$

Lemma 2.5: $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ path-cycle-based $s$,$t$-flow. Then, $(x_e) \in \IR^E$ defined by $x_e \coloneqq \sum_{p \in \PathSet\cup\CycleSet: e \in p}x_p$
Lemma 2.5: is non-negative flow, satisfies flow conservation at all nodes $v \in V \setminus \set{s,t}$ and has same value as $(x_p)$.

Lemma 2.6: $(x_e) \in \IR^E$ feasible $s$,$t$-flow. Then, there exists path-cycle-decomposition $(x_p) \in \IR^{\PathSet\cup\CycleSet}$ of $(x_e)$ such that
Lemma 2.5:mm $\fvals{(x_p)} = \fvals{(x_p)}$ and $\abs{\supp((x_e))} \leq \abs{\supp((x_e))}$
Lemma 2.6: Moreover, there exists path-based $s$,$t$-flow $(y_p) \in \IR^{\PathSet}$ such that
Lemma 2.5:mm $\fvals{(y_p)} = \fvals{(x_p)}$ and $y_e \coloneqq \sum_{p \in \PathSet\cup\CycleSet: e \in p}y_p \leq x_e$ f.a. $e \in E$

Lemma 2.3: $x,y \in \IR^E, \alpha \in \IR, z \coloneqq x+\alpha\cdot y$. Then

$x,y$ satisfy flow cons. at $v$ $\implies$ $z$ satisfies flow cons. at $v$
$x$ $s$,$t$-flow, $y$ satisfies flow cons. at $v \neq s,t$, $\mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)\geq 0$, $0 \leq z \leq \nu$
$\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)$
$x$ $s$,$t$-flow, $y = \chi_p$ for $p \in \PathSet$, $\alpha\geq -\mathrm{value}(x)$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in p$ $\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha$
$x$ $s$,$t$-flow, $y = \chi_c$ for $c \in \CycleSet$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in c$ $\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)$

§2.1 Maximum $s$,$t$-Flows

$(x_e)$ maximum $s$,$t$-flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} \leq \fvals{x}$

Theorem 2.8: For any $s$,$t$-network $N=(G,s,t,\nu)$ there exists a maximum $s$,$t$-flow in $N$.

Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x^* \in K: f(x^*) = \sup\Set{f(x) \SMid x \in K}$

bidirected graph $G^\leftrightarrow = (V,E^\leftrightarrow)$ with $E^\leftrightarrow \coloneqq E \,\,\dot{\cup}\,\, \set{e^\leftarrow \coloneqq wv \smid e=vw \in E}$
residual capacity $\nu_e^x \coloneqq \nu_e-x_e$ and $\nu_{e^\leftarrow}^x \coloneqq x_e$
residual graph $G^x = (V,E^x)$ with $E^x \coloneqq \set{e \in E^\leftrightarrow | \nu_e^x \gt 0}$
residual network $N^x = (G^x,s,t,\nu^x)$
augmenting $x$ along $p$ by $\alpha$ gives $(y_e)$ with $y_e \coloneqq \begin{cases}x_e+\alpha, &e \in p \text{ forward edge}\\x_e-\alpha, &e^\leftarrow \in p \text{ backward edge}\\x_e\end{cases}$

Alg. 1: Ford-Fulkerson Algorithm:
Input: $s$,$t$-network $N$
Output: maximum $s$,$t$-flow $x$ in $N$

Start with $x_e \leftarrow 0$ f.a. $e \in E$
While $\exists x$-augmenting $s$,$t$-path in $N^x$ Do
.. compute $\alpha \leftarrow \min\set{\nu^x_e \smid e \in p}$
.. augment $x$ along $p$ by $\alpha$

Lem. 2.12: $x \in \IRnn^E$ an $s$,$t$-flow, $p \in \PathSet$ an $x$-augmenting path, $\alpha \in \IRnn$ with $\alpha \leq \nu_e^x$ f.a. $e \in E$
Lem. 2.12: Then, augmenting $x$ along $p$ by $\alpha$ gives $s$,$t$-flow with value $\alpha$ more than $x$.

$(x_e) \in \IR^E$ (edge-based) $s$,$t$-flow:

$0 \leq x_e \leq \nu_e$ for all $e \in E$
$\sum_{e \in \edgesTo{v}}x_e = \sum_{e \in \edgesFrom{v}}x_e$ for all $v \in V\setminus\Set{s,t}$
$\mathrm{value}(x)\coloneqq \sum_{e \in \edgesTo{t}}x_e - \sum_{e \in \edgesFrom{t}}x_e \geq 0$

$A \subseteq V$ $s$,$t$-cut $\coloniff$ $s \in A, t \notin A$
⇝ has capacity $\ccaps{A} \coloneqq \sum_{e \in \edgesFrom{A}}\nu_e$

Lem. 2.14: For any $s$,$t$-flow $x$ and $s$,$t$-cut $A$ we have
Lem. 2.14: $\fvals{x} = \sum_{e \in \edgesFrom{A}}x_e - \sum_{e \in \edgesTo{A}}x_e \leq \ccaps{A}$.

Thm. 2.15: For any $s$,$t$-flow the following are equivalent:

$x$ is maximum $s$,$t$-flow
$\nexists$ any $x$-augmenting path
$\exists$ $s$,$t$-cut $A$: $\ccaps{A} = \fvals{x}$

Cor. 2.16: For any $s$,$t$-network $N$: $\max_{x\, s,t\text{-flow}}\fvals{x} = \min_{A\, s,t\text{-cut}}\ccaps{A}$ "Max-Flow Min-Cut Theorem"

Theorem 2.17:
Ford-Fulkerson is correct.

Cor. 2.18: For $\nu \in \INo^E$: FF computes integral $s$,$t$-flow $x^*$ and terminates after at most $\fvals{x^*}$ many augmentations.

§2.2 Min-Cost-Flows

$(x_e)$ min-cost flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} = \fvals{x} \implies \fcosts{y} \geq \fcosts{x}$

Theorem 2.20: For any $s$,$t$-network $N=(G,s,t,\nu,\gamma)$ and $v \in [0,v^*]$ there exists a min-cost flow of value $v$ in $N$.

Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x_* \in K: f(x_*) = \inf\Set{f(x) \SMid x \in K}$

node-labels $\ell_v \coloneqq \inf\set{\gamma_p \smid p \text{ a } s,v\text{-path}}$

Lemma 2.24: For any $N$ with all nodes reachable from $s$, the following are equivalent:

no cycles of negative cost
reduced costs w.r.t. $\ell$ are non-negative
$\exists \pi \in \IR^V: \gamma^\pi \geq 0$

reduced costs wrt. $\pi \in \IR^V$: $\gamma^\pi_{vw} \coloneqq \gamma_{vw} + \pi_v-\pi_w$

Lemma 2.27: $N^x$ without negative cycles and $p$ an efficient $s$,$t$-path.
mmmm Then, augmenting along $p$ does not create negative cycles.

Lemma 2.28: For any $s$,$t$-flow $x$:
mm $x$ min-cost-flow $\iff$ no negative cycles in $N^x$

Cycle-Cancelling-Algorithm:
Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$,
Input: value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$

Start with any $s$,$t$-flow $x$ of value $v$
While $\exists x$-augmenting cycle $c$ with $\gamma_c \lt 0$ Do
.. augment $x$ along $c$ by $\min\set{\nu^x_e \smid e \in c}$

Successive-Shortest-Path-Algorithm:
Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$ without cycles
Input: of negative cost, value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$

Start with zero flow $x$
While $\fvals{x} \lt v$ Do
.. compute efficient $s$,$t$-path $p$ in $N^x$
.. augment $x$ along $p$ by $\min\set{v-\fvals{x},\min\set{\nu^x_e \smid e \in c}}$

Thm. 2.29: SSP and CC are correct.

Cor. 2.30: If $\nu \in \INo^E$ and $v \in \INo$, then SSP terminates and produces integral flow.
Cor. 2.30:The same holds for CC if, additionally, the initial flow is integral.

flow dependent edge cost: $\gamma_e: \IRnn \to \IR$ (continuous and non-decreasing)
→ path-cost $\gamma_p: \IRnn^E \to \IR, (x_e) \mapsto \sum_{e \in p}\gamma_e(x_e)$

Theorem 2.32: The following are equivalent for a path-based flow $(x_p)$:

$(x_p)$ is Wardrop equilibrium, i.e. $x_p \gt 0 \implies \gamma_p(x) \leq \gamma_q(x)$ f.a. $p,q \in \PathSet$
$(x_p)$ satisfies $\sum_{p \in \PathSet}\gamma_p(x)(y_p-x_p) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$ “path-based variational inequality”
$(x_p)$ satisfies $\sum_{e \in E}\gamma_e(x_e)(y_e-x_e) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$ “edge-based variational inequality”
$(x_p)$ is optimal solution to $\min P(y) \coloneqq \sum_{e \in E}\int_0^{y_e}\gamma_e(z)dz$ s.t. $(y_p)$ has same value as $(x_p)$

Fundamental Theorem of Calculus (part.):
\[f: [a,b] \to \IR \text{ continuous } \implies F: [a,b] \to \IR, x \mapsto \int_a^x f(z)\diff z \text{ differentiable}\] with $\deriv F(x) = x$ for all $ \in [a,b]$.

Corollary 2.33: There always exists a Wardrop-equilibrium of any value.

Theorem 2.34: Let $(x_p),(y_p)$ be two Wardrop equilibria of the same value (in the same network)

Then we have $\gamma_e(x_x) = \gamma_e(y_e)$ for all $e \in E$
If $\gamma_e$ are stritly increasing, then we have $x_e=y_e$ for all $e \in E$.